package uestc.lj.basic.greedy;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 解决初始资金利润，求k个项目之后所能获得的利润最大
 *
 * @Author:Crazlee
 * @Date:2021/11/24
 */
public class Code04_IOP {
	/**
	 * 代表一个项目的结构
	 */
	public static class Node {
		/**
		 * 一个项目的花费
		 */
		public int pay;
		/**
		 * 一个项目的利润
		 */
		public int returnPay;

		public Node(int pay, int returnPay) {
			this.pay = pay;
			this.returnPay = returnPay;
		}
	}

	/**
	 * 按照花费排序，小的在前面
	 */
	public static class MinCostComparator implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			return o1.pay - o2.pay;
		}
	}

	/**
	 * 按照利润排序，大的在前面
	 */
	public static class MaxProfitComparator implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			return o2.returnPay - o1.returnPay;
		}
	}

	/**
	 * 寻找指定条件下利润最多的项目
	 *
	 * @param k       最多执行k个项目
	 * @param w       初始资金
	 * @param Profits 项目的利润数组
	 * @param Captial 项目的花费数组
	 * @return 最多项目的利润和
	 */
	public static int findMaximumCapital(int k, int w, int[] Profits, int[] Captial) {
		PriorityQueue<Node> minCostQueue = new PriorityQueue<>(new MinCostComparator());
		PriorityQueue<Node> maxProfitQueue = new PriorityQueue<>(new MaxProfitComparator());
		for (int i = 0; i < Profits.length; i++) {
			minCostQueue.add(new Node(Captial[i], Profits[i]));
		}
		for (int i = 0; i < k; i++) {
			while (!minCostQueue.isEmpty() && minCostQueue.peek().pay <= w) {
				maxProfitQueue.add(minCostQueue.poll());
			}
			//无法做剩下的项目
			if (maxProfitQueue.isEmpty()) {
				return w;
			}
			w += maxProfitQueue.poll().returnPay;
		}
		return w;
	}
}
